package com.ayuer.chapter08;

import java.util.Arrays;

public class BubbleSortDemo {

    public static void bubble(int[] arr, int j) {
        //j为未排序的区域的右边界
        if (j == 0) {
            return;
        }
        //temp为交换的位置
        int x = 0;
        for (int i = 0; i < j; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                //记录最后一次交换前的位置
                x = i;
            }
        }
        bubble(arr, x);
    }

    public static void bubble3(int[] arr) {
        //j为未排序的区域的右边界

        //temp为交换的位置
//        int j = arr.length - 1;
//        int x = 0;
//        do {
//            //{5, 4, 3, 2, 1};
//            //{2, 1, 3, 4, 5};
//            for (int i = 0; i < j; i++) {
//                if (arr[i] > arr[i + 1]) {
//                    int temp = arr[i];
//                    arr[i] = arr[i + 1];
//                    arr[i + 1] = temp;
//                    //每次记录最后交换的位置
//                    x = i;
//                }
//            }
//            //循环结束后
//            j = x;
//        }
//        while (j != 0);


        int j = arr.length - 1;
        while (j != 0) {
            int x = 0;//每次记录最后交换的位置
            for (int i = 0; i < j; i++) {
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    //每次记录最后交换的位置
                    x = i;
                }
            }
            j = x;
        }

//        int x = 0;
//        for (int i = 0; i < j; i++) {
//            if (arr[i] > arr[i + 1]) {
//                int temp = arr[i];
//                arr[i] = arr[i + 1];
//                arr[i + 1] = temp;
//                //记录最后一次交换前的位置
//                x = i;
//            }
//        }
    }


    public static void bubble2(int[] arr, int j) {


        //不是最优
        //{5, 4, 3, 2, 1};
        for (int i = 0; i < arr.length - 1; i++) {
//            int x = arr.length - 1 - i;
            for (int i2 = 0; i2 < arr.length - 1 - i; i2++) {
                if (arr[i2] > arr[i2 + 1]) {
                    int temp = arr[i2];
                    arr[i2] = arr[i2 + 1];
                    arr[i2 + 1] = temp;
                    //记录最后一次交换前的位置
//                    x = i2;
                }
            }
        }

    }

    public static void main(String[] args) {
        int[] arr = {5, 4, 3, 2, 1};
//        bubble(arr, arr.length - 1);
//        bubble2(arr, arr.length - 1);
        bubble3(arr);
        System.out.println(Arrays.toString(arr));
    }
}
